package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 17:44 2020/8/8
    给定一个非空二叉树，返回其最大路径和。
    路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
    输入: [-10,9,20,null,null,15,7]

               -10
               / \
              9  20
                /  \
               15   7

    输出: 42  15+20+7=42

 */

public class MaxPathSum {

    /**
     * 采用递归，使用全局变量记录ans  如果某个节点为负数可以忽略它（一个节点也可是一条路径）
     *
     * @param root
     * @return
     */
    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return ans;
    }

    /**
     * 思想:对于任意一个最大路径节点满足下面两个条件之一
     *     1.当前 val+left+right  构成的最大路径
     *     2.max(left+right)+val 并返回给上面进行回溯所构成的最大路径
     * @param root
     * @return
     */
    private int dfs(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        int left = Math.max(dfs(root.left), 0); //比0小的全都舍弃
        int right = Math.max(dfs(root.right), 0);
        ans = Math.max(left + right + val, ans); //只有中左右情况才能是最终结果  记录当前最大的值
        return Math.max(left, right) + val;//选择分支中最大值+当前val  因为上层来的路基只能走一侧
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
